package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/reconstruct-itinerary/
 */
public class Title332 {

    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> hash = new HashMap<>();
        for (List<String> edge : tickets) {
            hash.computeIfAbsent(edge.get(0), k -> new PriorityQueue<>()).offer(edge.get(1));
        }
        List<String> result = new LinkedList<>();
        //遍历边
        dfs(hash, result, "JFK");
        return result;
    }

    private void dfs(Map<String, PriorityQueue<String>> hash, List<String> result, String cur) {
        //判断该节点是否有出边
        PriorityQueue<String> queue = hash.getOrDefault(cur, new PriorityQueue<>());
        while (!queue.isEmpty()) {
            dfs(hash, result, queue.poll());
        }
        result.add(0, cur);
    }

    public static void main(String[] args) {

    }
}
